package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/2a49359695a544b8939c77358d29b7e6?tpId=13&tqId=1517966&ru=/ta/sql-quick-study&qru=/ta/sql-quick-study/question-ranking">
 * JZ65 矩阵中的路径</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 \begin{bmatrix} a & b & c &e \\ s & f & c & s \\ a & d & e& e\\ \end{bmatrix}\quad
 * ⎣
 * ⎡
 * ​
 * <p>
 * a
 * s
 * a
 * ​
 * <p>
 * b
 * f
 * d
 * ​
 * <p>
 * c
 * c
 * e
 * ​
 * <p>
 * e
 * s
 * e
 * ​
 * <p>
 * ⎦
 * ⎤
 * ​
 * 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
 *
 * @author or2
 * @date 2021年10月12日 时间: 9:47
 */
public class JZ65 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param matrix char字符型二维数组
     * @param word   string字符串
     * @return bool布尔型
     */
    public boolean hasPath(char[][] matrix, String word) {
        int lengthCol = matrix.length, lengthRow = matrix[0].length;
        char[] chars = word.toCharArray();
        for (int col = 0; col < lengthCol; col++)
            for (int row = 0; row < lengthRow; row++)
                if (dfs(matrix, chars, col, row, 0)) return true;
        return false;
    }

    private boolean dfs(char[][] matrix, char[] word2Chars, int col, int row, int index) {
        if (col < 0 || col >= matrix.length ||
                row < 0 || row >= matrix[0].length ||
                matrix[col][row] == '.')
            return false;

        if (matrix[col][row] == word2Chars[index])
            index++;
        else
            return false;

        if (index == word2Chars.length)
            return true;

        char temp = matrix[col][row];
        matrix[col][row] = '.';

        boolean res = dfs(matrix, word2Chars, col - 1, row, index) ||
                dfs(matrix, word2Chars, col + 1, row, index) ||
                dfs(matrix, word2Chars, col, row - 1, index) ||
                dfs(matrix, word2Chars, col, row + 1, index);

        matrix[col][row] = temp;
        return res;
    }
}
